package com.zql.JianZhiOffer;

import java.util.HashMap;
import java.util.Map;

/**
 * Created By ShuHua on 2022/4/26.
 */
public class Offer_10_I {
    private  static Map<Integer,Integer> map = new HashMap<>();
    public static void main(String[] args) {
        int fib = fib(1);
        System.out.println(fib);

    }

    /**
     * 使用map存储计算结果，因为会有重复计算
     * @param n
     * @return
     */
    public  static int fib(int n) {
        if(n<2) return n;
        if(map.containsKey(n)){
            return map.get(n);
        }else {

            int i = (fib(n - 1) + fib(n - 2)) % 1000000007;
            map.put(n,i);
            return i;
        }

    }
}
